package com.xjh.basestudy.lanqiaobei;

import java.util.ArrayList;
import java.util.List;

public class DFS {
    public static void main(String[] args) {
        /**深度优先搜索：一般会有n层for循环*/
        /**
         * 按照字典序输出自然数 1 到n 所有不重复的排列，即n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
         *
         * 1. 初始化与标记数组
         * ◦ 定义结果集 result 存储所有排列。
         * ◦ 创建 used 数组标记数字是否被使用过（索引从1开始）。
         * ◦ 初始化路径 path 记录当前选择的数字序列。
         * 2. 递归终止条件
         * 当路径长度等于 n 时，将当前路径的拷贝加入结果集（避免引用传递导致的修改）。
         * 3. 按字典序遍历数字
         * 每次从1到n依次尝试选择数字，确保生成的排列是字典序。
         * 4. DFS与回溯操作
         * ◦ 选择数字：标记 used[i] = true，并将 i 加入路径。
         * ◦ 递归调用：进入下一层决策树。
         * ◦ 回溯撤销：在递归返回后，将 i 从路径移除，并取消标记 used[i] = false。
         * */
        int n = 3;
        List<List<Integer>> permutations = permute(n);
        for (List<Integer> p : permutations) {
            System.out.println(p);
        }
    }

    public static List<List<Integer>> permute(int n) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[n + 1]; // 标记数字是否已使用
        dfsTest(n, new ArrayList<>(), used, result);
        return result;
    }

    private static void dfsTest(int n, List<Integer> path, boolean[] used, List<List<Integer>> result) {
        // 终止条件：路径长度等于n
        if (path.size() == n) {
            result.add(new ArrayList<>(path)); // 深拷贝保存结果
            return;
        }
        // 遍历所有可能的数字（按字典序尝试）
        for (int i = 1; i <= n; i++) {
            if (!used[i]) {
                // 选择当前数字
                used[i] = true;
                path.add(i);
                // 递归进入下一层
                dfsTest(n, path, used, result);
                // 回溯：撤销选择
                path.remove(path.size() - 1);
                used[i] = false;
            }
        }
    }
}

/**
 *
 步骤	路径	已用标记	操作
 1	[]	[F,F,F,F]	选择1 → 标记1，进入递归
 2	[1]	[T,F,F,F]	选择2 → 标记2，进入递归
 3	[1,2]	[T,T,F,F]	选择3 → 标记3，触发终止条件
 4	[1,2,3]	[T,T,T,F]	保存结果[1,2,3]，回溯到步骤3
 5	[1,2]	[T,T,F,F]	撤销选择3 → 继续循环无剩余数字
 6	[1]	[T,F,F,F]	撤销选择2 → 选择3，标记3
 7	[1,3]	[T,F,T,F]	选择2 → 标记2，触发终止条件
 8	[1,3,2]	[T,T,T,F]	保存结果[1,3,2]，回溯到步骤7
 *
 *
 *
 *
 * */


